import re
try:
    from _json import encode_basestring_ascii as c_encode_basestring_ascii
except ImportError:
    c_encode_basestring_ascii = None
try:
    from _json import make_encoder as c_make_encoder
except ImportError:
    c_make_encoder = None
ESCAPE = re.compile('[\\x00-\\x1f\\\\"\\b\\f\\n\\r\\t]')
ESCAPE_ASCII = re.compile('([\\\\"]|[^\\ -~])')
HAS_UTF8 = re.compile('[\\x80-\\xff]')
ESCAPE_DCT = {'\\': '\\\\',
 '"': '\\"',
 '\x08': '\\b',
 '\x0c': '\\f',
 '\n': '\\n',
 '\r': '\\r',
 '\t': '\\t'}
for i in range(32):
    ESCAPE_DCT.setdefault(chr(i), '\\u{0:04x}'.format(i))

INFINITY = float('1e66666')
FLOAT_REPR = repr

def encode_basestring(s):

    def replace(match):
        return ESCAPE_DCT[match.group(0)]


    return (('"' + ESCAPE.sub(replace, s)) + '"')



def py_encode_basestring_ascii(s):
    if (isinstance(s, str) and (HAS_UTF8.search(s) is not None)):
        s = s.decode('utf-8')

    def replace(match):
        s = match.group(0)
        try:
            return ESCAPE_DCT[s]
        except KeyError:
            n = ord(s)
            if (n < 65536):
                return '\\u{0:04x}'.format(n)
            else:
                n -= 65536
                s1 = (55296 | ((n >> 10) & 1023))
                s2 = (56320 | (n & 1023))
                return '\\u{0:04x}\\u{1:04x}'.format(s1, s2)


    return (('"' + str(ESCAPE_ASCII.sub(replace, s))) + '"')


encode_basestring_ascii = (c_encode_basestring_ascii or py_encode_basestring_ascii)

class JSONEncoder(object):
    item_separator = ', '
    key_separator = ': '

    def __init__(self, skipkeys = False, ensure_ascii = True, check_circular = True, allow_nan = True, sort_keys = False, indent = None, separators = None, encoding = 'utf-8', default = None):
        self.skipkeys = skipkeys
        self.ensure_ascii = ensure_ascii
        self.check_circular = check_circular
        self.allow_nan = allow_nan
        self.sort_keys = sort_keys
        self.indent = indent
        if (separators is not None):
            (self.item_separator, self.key_separator,) = separators
        if (default is not None):
            self.default = default
        self.encoding = encoding



    def default(self, o):
        raise TypeError((repr(o) + ' is not JSON serializable'))



    def encode(self, o):
        if isinstance(o, basestring):
            if isinstance(o, str):
                _encoding = self.encoding
                if (_encoding is not None):
                    if (not (_encoding == 'utf-8')):
                        o = o.decode(_encoding)
                if self.ensure_ascii:
                    return encode_basestring_ascii(o)
                else:
                    return encode_basestring(o)
            chunks = self.iterencode(o, _one_shot=True)
            if not isinstance(chunks, (list, tuple)):
                chunks = list(chunks)
            return ''.join(chunks)



    def iterencode(self, o, _one_shot = False):
        if self.check_circular:
            markers = {}
        else:
            markers = None
        if self.ensure_ascii:
            _encoder = encode_basestring_ascii
        else:
            _encoder = encode_basestring
        if (self.encoding != 'utf-8'):

            def _encoder(o, _orig_encoder = _encoder, _encoding = self.encoding):
                if isinstance(o, str):
                    o = o.decode(_encoding)
                return _orig_encoder(o)



        def floatstr(o, allow_nan = self.allow_nan, _repr = FLOAT_REPR, _inf = INFINITY, _neginf = -INFINITY):
            if (o != o):
                text = 'NaN'
            elif (o == _inf):
                text = 'Infinity'
            elif (o == _neginf):
                text = '-Infinity'
            else:
                return _repr(o)
            if not allow_nan:
                raise ValueError(('Out of range float values are not JSON compliant: ' + repr(o)))
            return text


        if ((_one_shot and (c_make_encoder is not None)) and ((not self.indent) and (not self.sort_keys))):
            _iterencode = c_make_encoder(markers, self.default, _encoder, self.indent, self.key_separator, self.item_separator, self.sort_keys, self.skipkeys, self.allow_nan)
        else:
            _iterencode = _make_iterencode(markers, self.default, _encoder, self.indent, floatstr, self.key_separator, self.item_separator, self.sort_keys, self.skipkeys, _one_shot)
        return _iterencode(o, 0)




def _make_iterencode(markers, _default, _encoder, _indent, _floatstr, _key_separator, _item_separator, _sort_keys, _skipkeys, _one_shot, ValueError = ValueError, basestring = basestring, dict = dict, float = float, id = id, int = int, isinstance = isinstance, list = list, long = long, str = str, tuple = tuple):

    def _iterencode_list(lst, _current_indent_level):
        if not lst:
            yield '[]'
            return 
        if (markers is not None):
            markerid = id(lst)
            if (markerid in markers):
                raise ValueError('Circular reference detected')
            markers[markerid] = lst
        buf = '['
        if (_indent is not None):
            _current_indent_level += 1
            newline_indent = ('\n' + (' ' * (_indent * _current_indent_level)))
            separator = (_item_separator + newline_indent)
            buf += newline_indent
        else:
            newline_indent = None
            separator = _item_separator
        first = True
        for value in lst:
            if first:
                first = False
            else:
                buf = separator
            if isinstance(value, basestring):
                yield (buf + _encoder(value))
            elif (value is None):
                yield (buf + 'null')
            elif (value is True):
                yield (buf + 'true')
            else:
                if (value is False):
                    yield (buf + 'false')
            if isinstance(value, (int, long)):
                yield (buf + str(value))
            elif isinstance(value, float):
                yield (buf + _floatstr(value))
            else:
                yield buf
                if isinstance(value, (list, tuple)):
                    chunks = _iterencode_list(value, _current_indent_level)
                elif isinstance(value, dict):
                    chunks = _iterencode_dict(value, _current_indent_level)
                else:
                    chunks = _iterencode(value, _current_indent_level)
                for chunk in chunks:
                    yield chunk


        if (newline_indent is not None):
            _current_indent_level -= 1
            yield ('\n' + (' ' * (_indent * _current_indent_level)))
        yield ']'
        if (markers is not None):
            del markers[markerid]



    def _iterencode_dict(dct, _current_indent_level):
        if not dct:
            yield '{}'
            return 
        if (markers is not None):
            markerid = id(dct)
            if (markerid in markers):
                raise ValueError('Circular reference detected')
            markers[markerid] = dct
        yield '{'
        if (_indent is not None):
            _current_indent_level += 1
            newline_indent = ('\n' + (' ' * (_indent * _current_indent_level)))
            item_separator = (_item_separator + newline_indent)
            yield newline_indent
        else:
            newline_indent = None
            item_separator = _item_separator
        first = True
        if _sort_keys:
            items = sorted(dct.items(), key=lambda kv: kv[0])
        else:
            items = dct.iteritems()
        for (key, value,) in items:
            if isinstance(key, basestring):
                pass
            elif isinstance(key, float):
                key = _floatstr(key)
            elif (key is True):
                key = 'true'
            elif (key is False):
                key = 'false'
            elif (key is None):
                key = 'null'
            elif isinstance(key, (int, long)):
                key = str(key)
            elif _skipkeys:
                continue
            else:
                raise TypeError((('key ' + repr(key)) + ' is not a string'))
            if first:
                first = False
            else:
                yield item_separator
            yield _encoder(key)
            yield _key_separator
            if isinstance(value, basestring):
                yield _encoder(value)
            elif (value is None):
                yield 'null'
            elif (value is True):
                yield 'true'
            else:
                if (value is False):
                    yield 'false'
            if isinstance(value, (int, long)):
                yield str(value)
            elif isinstance(value, float):
                yield _floatstr(value)
            elif isinstance(value, (list, tuple)):
                chunks = _iterencode_list(value, _current_indent_level)
            elif isinstance(value, dict):
                chunks = _iterencode_dict(value, _current_indent_level)
            else:
                chunks = _iterencode(value, _current_indent_level)
            for chunk in chunks:
                yield chunk


        if (newline_indent is not None):
            _current_indent_level -= 1
            yield ('\n' + (' ' * (_indent * _current_indent_level)))
        yield '}'
        if (markers is not None):
            del markers[markerid]



    def _iterencode(o, _current_indent_level):
        if isinstance(o, basestring):
            yield _encoder(o)
        elif (o is None):
            yield 'null'
        elif (o is True):
            yield 'true'
        elif (o is False):
            yield 'false'
        elif isinstance(o, (int, long)):
            yield str(o)
        elif isinstance(o, float):
            yield _floatstr(o)
        elif isinstance(o, (list, tuple)):
            for chunk in _iterencode_list(o, _current_indent_level):
                yield chunk

        elif isinstance(o, dict):
            for chunk in _iterencode_dict(o, _current_indent_level):
                yield chunk

        elif (markers is not None):
            markerid = id(o)
            if (markerid in markers):
                raise ValueError('Circular reference detected')
            markers[markerid] = o
        o = _default(o)
        for chunk in _iterencode(o, _current_indent_level):
            yield chunk

        if (markers is not None):
            del markers[markerid]


    return _iterencode



